{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Rotation with Highest Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestRotation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得分最高的最小轮调"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>nums</code>，我们可以将它按一个非负整数 <code>k</code> 进行轮调，这样可以使数组变为&nbsp;<code>[nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]</code>&nbsp;的形式。此后，任何值小于或等于其索引的项都可以记作一分。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，数组为&nbsp;<code>nums = [2,4,1,3,0]</code>，我们按&nbsp;<code>k = 2</code>&nbsp;进行轮调后，它将变成&nbsp;<code>[1,3,0,2,4]</code>。这将记为 <code>3</code> 分，因为 <code>1 &gt; 0</code> [不计分]、<code>3 &gt; 1</code> [不计分]、<code>0 &lt;= 2</code> [计 1 分]、<code>2 &lt;= 3</code> [计 1 分]，<code>4 &lt;= 4</code> [计 1 分]。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 <code>k</code> 。如果有多个答案，返回满足条件的最小的下标 <code>k</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,1,4,0]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "下面列出了每个 k 的得分：\n",
    "k = 0,  nums = [2,3,1,4,0],    score 2\n",
    "k = 1,  nums = [3,1,4,0,2],    score 3\n",
    "k = 2,  nums = [1,4,0,2,3],    score 3\n",
    "k = 3,  nums = [4,0,2,3,1],    score 4\n",
    "k = 4,  nums = [0,2,3,1,4],    score 3\n",
    "所以我们应当选择&nbsp;k = 3，得分最高。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,0,2,4]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "nums 无论怎么变化总是有 3 分。\n",
    "所以我们将选择最小的 k，即 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-rotation-with-highest-score](https://leetcode.cn/problems/smallest-rotation-with-highest-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-rotation-with-highest-score](https://leetcode.cn/problems/smallest-rotation-with-highest-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,4,0]', '[1,3,0,2,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        \n",
    "        # rs = 0\n",
    "        # for index, value in enumerate(nums):\n",
    "        #     if value <= index:\n",
    "        #         rs += 1\n",
    "        # min_k = 0\n",
    "        # min_score = rs\n",
    "        # # 反向遍历k\n",
    "        # n = len(nums)\n",
    "        # for k in range(n-1, 0):\n",
    "        #     head = nums[0]\n",
    "        #     nums = nums[1:]\n",
    "        #     nums.append(head)\n",
    "\n",
    "        #     if head <= n-1:\n",
    "        #         rs += 1\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n+1)\n",
    "\n",
    "        for index ,value in enumerate(nums):\n",
    "            if value > index:\n",
    "                left = index +1\n",
    "                right = index + n - value\n",
    "                diff[left] += 1\n",
    "                diff[right+1] -= 1\n",
    "            elif value <= index:\n",
    "                left1 = 0\n",
    "                right1 = index - value\n",
    "                diff[left1] += 1\n",
    "                diff[right1+1] -=1\n",
    "\n",
    "                left2 = index +1\n",
    "                right2 = n-1\n",
    "                diff[left2] +=1\n",
    "                diff[right2+1] -=1\n",
    "\n",
    "        score, max_score, index = 0,0,0\n",
    "        for i, d in enumerate(diff):\n",
    "            score += d\n",
    "            if score > max_score:\n",
    "                max_score = score\n",
    "                index = i\n",
    "        return index\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "\n",
    "        for i , num in enumerate(nums):\n",
    "            if num <= i:\n",
    "                diff[0] += 1\n",
    "                diff[i+1] += 1\n",
    "                diff[i-num+1] -= 1\n",
    "            else:\n",
    "                diff[i+1] += 1\n",
    "                diff[i+n-num+1] -= 1\n",
    "\n",
    "        s = 0\n",
    "        p = 0\n",
    "        ans = 0\n",
    "        for i , num in enumerate(diff):\n",
    "            s += num\n",
    "            if s > p:\n",
    "                s = p\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: list[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        下面列出了每个 k 的得分：\n",
    "        k = 0,  nums = [2,3,1,4,0],    score 2\n",
    "        k = 1,  nums = [3,1,4,0,2],    score 3\n",
    "        k = 2,  nums = [1,4,0,2,3],    score 3\n",
    "        k = 3,  nums = [4,0,2,3,1],    score 4\n",
    "        k = 4,  nums = [0,2,3,1,4],    score 3\n",
    "\n",
    "\n",
    "        元素 x 得分的下标范围是 [x, n-1]，有 n - x 个元素。\n",
    "\n",
    "        假设元素 x 初始下标为 i，论调下表为 k。\n",
    "        此时元素 x 的下标是 (i - k + n) % n。\n",
    "        有 0 <= (i - k + n) % n <= n-1\n",
    "\n",
    "\n",
    "\n",
    "        如果得分，则有 (i - k + n) % n >= x。\n",
    "        等价于 k <= (i + n - x) % n。\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            \n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "\n",
    "        score, max_score, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > max_score:\n",
    "                max_score, idx = score, i\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        # num ---> n - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            if i >= num:\n",
    "                diff[0] += 1\n",
    "                diff[i - num + 1] -= 1\n",
    "                diff[i + 1] += 1\n",
    "            else:\n",
    "                diff[i + 1] += 1\n",
    "                diff[i - num + n + 1] -= 1\n",
    "        ans = cur = mx = 0\n",
    "        for i in range(n):\n",
    "            cur += diff[i]\n",
    "            if cur > mx:\n",
    "                ans, mx = i, cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        # 当前位置 - 目标位置 + n mod n\n",
    "        # (i-nums[i]+n) % n -- 可能的最多移动次数\n",
    "        # (i+1)%n -- 可能的最少移动次数\n",
    "# (i+1)%n<=k<=(i−nums[i]+n)%n\n",
    "        n = len(nums)\n",
    "        c = [0] * (n + 1)\n",
    "        for i, v in enumerate(nums):\n",
    "            # 类似于 3~1 这种循环了，分成了两段，一段是3~4，一段是0~1，把0的位置补上一个1即可\n",
    "            if i >= v: # [v, n-1]\n",
    "                c[0] += 1 \n",
    "                c[i-v+1] -= 1   \n",
    "                c[i+1] += 1     \n",
    "            else:\n",
    "                c[i+1] += 1     \n",
    "                c[i-v+n+1] -= 1 \n",
    "\n",
    "        ans = cur = mx = 0\n",
    "        for i in range(n):\n",
    "            cur += c[i]\n",
    "            if cur > mx:\n",
    "                ans, mx = i, cur\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            if i < x:\n",
    "                l, r = i + 1, i - x + n\n",
    "                diff[l] += 1\n",
    "                diff[r + 1] -= 1\n",
    "            elif i >= x:\n",
    "                l, r = 0, i - x\n",
    "                diff[l] += 1\n",
    "                diff[r + 1] -= 1\n",
    "                l, r = i + 1, n - 1\n",
    "                diff[l] += 1\n",
    "                diff[r + 1] -= 1\n",
    "            \n",
    "        pre = mx = ans = 0\n",
    "        for i in range(n + 1):\n",
    "            pre += diff[i]\n",
    "            if pre > mx:\n",
    "                mx = pre\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x <= i:\n",
    "                diff[0] += 1\n",
    "                diff[i - x + 1] -= 1\n",
    "                diff[i + 1] += 1\n",
    "            else: # x > i\n",
    "                diff[i + 1] += 1\n",
    "                mv = n - x\n",
    "                diff[i + 1 + mv] -= 1\n",
    "        mx, k = 0, 0\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += diff[i]\n",
    "            if s > mx:\n",
    "                mx, k = s, i\n",
    "        return k\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n # Remember\n",
    "            high = (i - num + n + 1) % n # Remember\n",
    "            diff[low] += 1\n",
    "            diff[high] -= 1\n",
    "            if low >= high:\n",
    "                diff[0] += 1\n",
    "        max_score, now_score, ans = 0, 0, -1\n",
    "        for i in range(n):\n",
    "            now_score += diff[i]\n",
    "            if now_score > max_score:\n",
    "                max_score = now_score  \n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            x= nums[i]\n",
    "            low = (i+1)%n\n",
    "            high = (n+i-x) %n\n",
    "            diff[low]+=1\n",
    "            if high<n-1:\n",
    "                diff[high+1] -=1\n",
    "            if low > high:\n",
    "                diff[0] +=1\n",
    "        max_score = diff[0]\n",
    "        ans = 0\n",
    "        score = diff[0]\n",
    "        for i in range(1,n):\n",
    "            score += diff[i]\n",
    "            if score > max_score:\n",
    "                ans = i\n",
    "                score = max_score\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bestRotation(self, nums: List[int]) -> int:\r\n",
    "        L=len(nums)\r\n",
    "        # Max_idx=L-1\r\n",
    "        diff=[0]*L\r\n",
    "        \r\n",
    "        for i,n in enumerate(nums):\r\n",
    "            if n>=L:\r\n",
    "                continue\r\n",
    "            # if n==0:\r\n",
    "            #     diff[0]+=1\r\n",
    "            #     continue\r\n",
    "            if n<=i:\r\n",
    "                diff[0]+=1\r\n",
    "                if i-n+1<L:\r\n",
    "                    diff[i-n+1]-=1\r\n",
    "                if i+1<L:\r\n",
    "                    diff[i+1]+=1\r\n",
    "                # diff[L-1+1]-=1\r\n",
    "            else:\r\n",
    "                least_move=i+1\r\n",
    "                most_move=L-1-n+least_move\r\n",
    "                diff[least_move]+=1\r\n",
    "                if most_move+1<L:\r\n",
    "                    diff[most_move+1]-=1\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        cur_p=0\r\n",
    "        max_p=0\r\n",
    "        for i,k in enumerate(diff):\r\n",
    "            cur_p+=k\r\n",
    "            if cur_p>max_p:\r\n",
    "                max_p=cur_p\r\n",
    "                ret=i\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            if i >= x:\n",
    "                diff[0] += 1\n",
    "                diff[i - x + 1] -= 1\n",
    "                diff[i + 1] += 1\n",
    "            else:\n",
    "                diff[i + 1] += 1\n",
    "                #n - y >= x\n",
    "                diff[i + 1 + n - x] -= 1\n",
    "            # print(f'i={i}, diff={diff}')\n",
    "        \n",
    "        s, mx, k = 0, 0,  0\n",
    "        for i in range(n):\n",
    "            s += diff[i]\n",
    "            if s > mx:\n",
    "                mx = s\n",
    "                k = i\n",
    "        return k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        # n[i] 对应 (i-k+n) mod n\n",
    "        # 如果n[i] <= (i-k+n) mod n --> ans += 1\n",
    "        # len(n) -- 10^5 -- O(n) - O(nlogn)\n",
    "        # 何时n[i]能得分 k <= i - n[i]\n",
    "        # k的取值范围 [0, n-1]\n",
    "        # 能得分的k的取值范围 [i-(n-1), i-n[i]]\n",
    "        # 考虑取模 -- 1. [i-(n-1), i-n[i]] 2. [0, i-n[i]] + [i-(n-1), n-1]\n",
    "        n = len(nums)\n",
    "        c = [0] * (n + 1)\n",
    "        for i, v in enumerate(nums):\n",
    "            if i >= v: # [v, n-1]\n",
    "                c[0] += 1 # 不移动时，就可以产生一个贡献值\n",
    "            c[i+1] += 1     # 出0路径:   i, i-1, ..., 1, 0, n-1 共移动了 i+1 次。\n",
    "            c[(i+n-v+1) % n] -= 1 # 入n-1路径：i, i-1, ..., 0, n-1, n-2, ..., num+1,num,num-1。共移动了 i+ n-num+1次。 \n",
    "        ans = cur = mx = 0\n",
    "        for i in range(n):\n",
    "            cur += c[i]\n",
    "            if cur > mx:\n",
    "                ans, mx = i, cur\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            x= nums[i]\n",
    "            low = (i+1)%n\n",
    "            high = (n+i-x+1) %n\n",
    "            diff[low]+=1\n",
    "            diff[high] -=1\n",
    "            if low >= high:\n",
    "                diff[0] +=1\n",
    "        max_score = diff[0]\n",
    "        ans = 0\n",
    "        score = diff[0]\n",
    "        for i in range(1,n):\n",
    "            score += diff[i]\n",
    "            if score > max_score:\n",
    "                ans = i\n",
    "                score = max_score\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        # n[i] 对应 (i-k+n) mod n\n",
    "        # 如果n[i] <= (i-k+n) mod n --> ans += 1\n",
    "        # len(n) -- 10^5 -- O(n) - O(nlogn)\n",
    "        # 何时n[i]能得分 k <= i - n[i]\n",
    "        # k的取值范围 [0, n-1]\n",
    "        # 能得分的k的取值范围 [i-(n-1), i-n[i]]\n",
    "        # 考虑取模 -- 1. [i-(n-1), i-n[i]] 2. [0, i-n[i]] + [i-(n-1), n-1]\n",
    "        n = len(nums)\n",
    "        c = [0] * (n + 1)\n",
    "        for i, v in enumerate(nums):\n",
    "            if i >= v: # [v, n-1]\n",
    "                c[0] += 1 # 不移动时，就可以产生一个贡献值\n",
    "                c[i-v+1] -= 1   # 出num路径: i, i-1, num, num-1。 共移动了 i-(num-1) = i-num+1 次。\n",
    "                c[i+1] += 1     # 入n-1路径: i, i-1, num, num-1,num-2,...,0,n-1。 共移动了 i+1 次。\n",
    "            else:\n",
    "                # 一开始所在位置不可得分；左移是没有用的；只有移动到边界时，才会产生变化\n",
    "                c[i+1] += 1     # 出0路径: i, i-1, ..., 1, 0, n-1 共移动了 i+1 次。\n",
    "                c[i-v+n+1] -= 1 # 入num-1路径：i, i-1, ..., 0, n-1, n-2, ..., num+1,num,num-1。共移动了 i+ n-num+1次。 \n",
    "\n",
    "        ans = cur = mx = 0\n",
    "        for i in range(n):\n",
    "            cur += c[i]\n",
    "            if cur > mx:\n",
    "                ans, mx = i, cur\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bestRotation(self, nums: List[int]) -> int:\r\n",
    "        L=len(nums)\r\n",
    "        # Max_idx=L-1\r\n",
    "        diff=[0]*L\r\n",
    "        \r\n",
    "        for i,n in enumerate(nums):\r\n",
    "            if n>=L:\r\n",
    "                continue\r\n",
    "            if n==0:\r\n",
    "                diff[0]+=1\r\n",
    "                continue\r\n",
    "            if n<=i:\r\n",
    "                diff[0]+=1\r\n",
    "                if i-n+1<L:\r\n",
    "                    diff[i-n+1]-=1\r\n",
    "                if i+1<L:\r\n",
    "                    diff[i+1]+=1\r\n",
    "                # diff[L-1+1]-=1\r\n",
    "            else:\r\n",
    "                least_move=i+1\r\n",
    "                most_move=L-1-n+least_move\r\n",
    "                diff[least_move]+=1\r\n",
    "                if most_move+1<L:\r\n",
    "                    diff[most_move+1]-=1\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        cur_p=0\r\n",
    "        max_p=0\r\n",
    "        for i,k in enumerate(diff):\r\n",
    "            cur_p+=k\r\n",
    "            if cur_p>max_p:\r\n",
    "                max_p=cur_p\r\n",
    "                ret=i\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diffs = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            low = (i + 1) % n\n",
    "            high = (i - num + n + 1) % n\n",
    "            diffs[low] += 1\n",
    "            diffs[high] -= 1\n",
    "            if low >= high:\n",
    "                diffs[0] += 1\n",
    "        score, maxScore, idx = 0, 0, 0\n",
    "        for i, diff in enumerate(diffs):\n",
    "            score += diff\n",
    "            if score > maxScore:\n",
    "                maxScore, idx = score, i\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        has = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            has[i+1] += 1\n",
    "            has[(i-nums[i]+1)%n] -= 1\n",
    "        sm, mx, mxn = 0, has[0], 0\n",
    "        for i in range(n):\n",
    "            sm += has[i]\n",
    "            if sm > mx: mx, mxn = sm, i\n",
    "        return mxn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            if i >= num:\n",
    "                diff[0] += 1\n",
    "                diff[i - num + 1] -= 1\n",
    "                diff[i + 1] += 1\n",
    "            else:\n",
    "                diff[i + 1] += 1\n",
    "                diff[i - num + n + 1] -= 1\n",
    "        res = cur = max = 0\n",
    "        for i in range(n):\n",
    "            cur += diff[i]\n",
    "            if cur > max:\n",
    "                res, max = i, cur\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def bestRotation(self, nums: List[int]) -> int:\r\n",
    "        L=len(nums)\r\n",
    "        # Max_idx=L-1\r\n",
    "        diff=[0]*L\r\n",
    "        \r\n",
    "        for i,n in enumerate(nums):\r\n",
    "            low=(1+i)%L\r\n",
    "            high=(L+i-n+1)%L\r\n",
    "            diff[low]+=1\r\n",
    "            diff[high]-=1\r\n",
    "            if low>=high:\r\n",
    "                diff[0]+=1\r\n",
    "            # if n>=L:\r\n",
    "            #     continue\r\n",
    "            # # if n==0:\r\n",
    "            # #     diff[0]+=1\r\n",
    "            # #     continue\r\n",
    "            # if n<=i:\r\n",
    "            #     diff[0]+=1\r\n",
    "            #     if i-n+1<L:\r\n",
    "            #         diff[i-n+1]-=1\r\n",
    "            #     if i+1<L:\r\n",
    "            #         diff[i+1]+=1\r\n",
    "            #     # diff[L-1+1]-=1\r\n",
    "            # else:\r\n",
    "            #     least_move=i+1\r\n",
    "            #     most_move=L-1-n+least_move\r\n",
    "            #     diff[least_move]+=1\r\n",
    "            #     if most_move+1<L:\r\n",
    "            #         diff[most_move+1]-=1\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        cur_p=0\r\n",
    "        max_p=0\r\n",
    "        for i,k in enumerate(diff):\r\n",
    "            cur_p+=k\r\n",
    "            if cur_p>max_p:\r\n",
    "                max_p=cur_p\r\n",
    "                ret=i\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1.\n",
    "nums[i] = x -> (i - k + n) % n\n",
    "x <= (i - k + n) % n\n",
    "k <= (i - x + n) % n\n",
    "2.\n",
    "(i - k + n) % n <= n - 1\n",
    "k >= (i + 1) % n\n",
    "'''\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        d = [0] * 100010\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            a = (i + 1) % n\n",
    "            b = (i - x + n) % n\n",
    "            if a <= b:\n",
    "                d[a] += 1\n",
    "                d[b + 1] -= 1\n",
    "            else:\n",
    "                d[0] += 1\n",
    "                d[b + 1] -= 1\n",
    "                d[a] += 1\n",
    "                d[n] -= 1\n",
    "        mx = 0\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur += d[i]\n",
    "            if cur > mx:\n",
    "                ans = i\n",
    "                mx = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums):\n",
    "        n = len(nums)\n",
    "        change_score = [0] * (n+1)\n",
    "        for i, num in enumerate(nums):\n",
    "            # num > n 肯定不会加分，直接不考虑\n",
    "            if num <= n:\n",
    "                if num > i:\n",
    "                    change_score[i+1] += 1\n",
    "                    change_score[n-num+i+1] -= 1\n",
    "                else:\n",
    "                    # equal to [0,i-num] and [i+1, n-1] add 1\n",
    "                    change_score[i-num+1] += -1\n",
    "                    change_score[i+1] -= -1\n",
    "        change_score.pop()\n",
    "        for i in range(1,n):\n",
    "            change_score[i] = change_score[i] + change_score[i-1]\n",
    "        \n",
    "        # 找到第一个k使得分最多\n",
    "        return change_score.index(max(change_score))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums):\n",
    "        n = len(nums)\n",
    "        change_score = [0] * (n+1)\n",
    "        for i, num in enumerate(nums):\n",
    "            # num > n 肯定不会加分，直接不考虑\n",
    "            if num <= n:\n",
    "                if num > i:\n",
    "                    change_score[i+1] += 1\n",
    "                    change_score[n-num+i+1] -= 1\n",
    "                else:\n",
    "                    # equal to [0,i-num] and [i+1, n-1] add 1\n",
    "                    change_score[i-num+1] += -1\n",
    "                    change_score[i+1] -= -1\n",
    "        change_score.pop()\n",
    "        for i in range(1,n):\n",
    "            change_score[i] = change_score[i] + change_score[i-1]\n",
    "        \n",
    "        # 找到第一个k使得分最多\n",
    "        return change_score.index(max(change_score))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums):\n",
    "        n = len(nums)\n",
    "        change = [1] * n  # 初始化数组 change，表示旋转后的得分变化\n",
    "        for i in range(n):\n",
    "            change[(i - nums[i] + 1) % n] -= 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            change[i] += change[i - 1]\n",
    "\n",
    "        best_rotation = change.index(max(change))\n",
    "        return best_rotation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums):\n",
    "        n = len(nums)\n",
    "        change = [1] * n  # 初始化数组 change，表示旋转后的得分变化\n",
    "        for i in range(n):\n",
    "            change[(i - nums[i] + 1) % n] -= 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            change[i] += change[i - 1]\n",
    "\n",
    "        best_rotation = change.index(max(change))\n",
    "        return best_rotation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums):\n",
    "        n = len(nums)\n",
    "        change = [1] * n\n",
    "        for i in range(n):\n",
    "            change[(i - nums[i] + 1) % n] -= 1\n",
    "        for i in range(1, n):\n",
    "            change[i] += change[i - 1]\n",
    "\n",
    "        return change.index(max(change))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 差分数组版本\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        # 计算每个值在轮调几次可以贡献分数，发现轮调次数都是连续的，对可轮调区间标记，标记最多的就是答案\n",
    "        # 对连续区间标记，可以用线段树和差分数组\n",
    "        # 2:1,2,3\n",
    "        # 3:2,3\n",
    "        # 1:0,1,3,4\n",
    "        # 4:4\n",
    "        # 0:0,1,2,3,4\n",
    "        # 得到c[] = [2, 3, 3, 4, 3]，答案为最大的indx=3\n",
    "\n",
    "        # 对于arr[i] = x，轮调0~i次会变小（i~0），i+1~n-1次会变大(n-1~i+1)\n",
    "        # 如果x>i，0~i次轮调都没有分数，如果x<=i，轮调[0,i-x]次有分数\n",
    "        # 如果x>n-1，i+1~n-1次都没有分数，如果x<=n-1，轮调[i+1, i+n-x]\n",
    "        n = len(nums)\n",
    "        c = [0]*(n+1)\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            if x<=i:\n",
    "                c[0]+=1\n",
    "                c[i-x+1]-=1\n",
    "            if x<=n-1:\n",
    "                c[i+1]+=1\n",
    "                r = min(n-1, i+n-x)\n",
    "                c[r+1]-=1\n",
    "        res, resi = c[0],0\n",
    "        for i in range(1,n):\n",
    "            c[i] += c[i-1]\n",
    "            if c[i] > res:\n",
    "                res,resi = c[i],i\n",
    "\n",
    "        return resi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, x in enumerate(nums):\n",
    "            if i < x:  # k in [i + 1, n - x + i]\n",
    "                diff[i + 1] += 1\n",
    "                diff[n - x + i + 1] -= 1\n",
    "            else:  # k in [0, i - x] or [i + 1, n - 1]\n",
    "                diff[0] += 1\n",
    "                diff[i - x + 1] -= 1\n",
    "                diff[i + 1] += 1\n",
    "                diff[n] -= 1\n",
    "        ans = 0\n",
    "        cur = mx = 0\n",
    "        for i, x in enumerate(diff[:-1]):\n",
    "            cur += x\n",
    "            if mx < cur:\n",
    "                mx = cur\n",
    "                ans = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt_minus = [0]*n\n",
    "        cnt_plus = [0]*n\n",
    "        res = 0\n",
    "        maxi = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            maxi += int(x<=i)\n",
    "            cnt_plus[(i+1)%n] += 1\n",
    "            cnt_minus[(i-x+1)%n] += 1\n",
    "        cur = maxi\n",
    "        for k in range(1,n):\n",
    "            cur += cnt_plus[k]-cnt_minus[k]\n",
    "            if cur>maxi:\n",
    "                res = k\n",
    "                maxi = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      diff = [0] * (n + 1)\n",
    "      for i in range(n):\n",
    "        diff[i + 1] += 1\n",
    "        if nums[i] <= i:\n",
    "          diff[0] += 1\n",
    "          diff[i - nums[i] + 1] -= 1\n",
    "          diff[-1] -= 1\n",
    "        else:\n",
    "          diff[n + 1 + i - nums[i]] -= 1\n",
    "      \n",
    "      for i in range(1, n + 1):\n",
    "        diff[i] += diff[i-1]\n",
    "      \n",
    "      maxIdx = 0\n",
    "      for i in range(1, n):\n",
    "        if diff[i] > diff[maxIdx]:  maxIdx = i\n",
    "      return maxIdx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (n + 1)\n",
    "        def insert(l, r):\n",
    "            diff[l] += 1\n",
    "            diff[r + 1] -= 1\n",
    "        for i, x in enumerate(nums):\n",
    "            l, r = (i - n + 1) % n, (i - x) % n\n",
    "            if l <= r:\n",
    "                insert(l, r)\n",
    "            else:\n",
    "                insert(0, r)\n",
    "                insert(l, n - 1)\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            diff[i] += diff[i - 1]\n",
    "            if diff[i] > diff[ans]:\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      diff = [0] * (n + 1)\n",
    "      for i in range(n):\n",
    "        diff[i + 1] += 1\n",
    "        if nums[i] <= i:\n",
    "          diff[0] += 1\n",
    "          diff[i - nums[i] + 1] -= 1\n",
    "          diff[-1] -= 1\n",
    "        else:\n",
    "          diff[n + 1 + i - nums[i]] -= 1\n",
    "      \n",
    "      maxIdx = 0\n",
    "      for i in range(1, n + 1):\n",
    "        diff[i] += diff[i-1]\n",
    "        if diff[i] > diff[maxIdx]:  maxIdx = i\n",
    "    \n",
    "      return maxIdx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      diff = [0] * (n + 1)\n",
    "      for i in range(n):\n",
    "        diff[i + 1] += 1\n",
    "        if nums[i] <= i:\n",
    "          diff[0] += 1\n",
    "          diff[i - nums[i] + 1] -= 1\n",
    "          diff[-1] -= 1\n",
    "        else:\n",
    "          diff[n + 1 + i - nums[i]] -= 1\n",
    "      \n",
    "      for i in range(1, n + 1):\n",
    "        diff[i] += diff[i-1]\n",
    "      \n",
    "      maxIdx = 0\n",
    "      for i in range(1, n):\n",
    "        if diff[i] > diff[maxIdx]:  maxIdx = i\n",
    "      return maxIdx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dif=[0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==0:\n",
    "                dif[0]+=1\n",
    "                continue\n",
    "            if x<=i:\n",
    "                dif[0]+=1\n",
    "                dif[i-(x-1)]-=1\n",
    "                dif[i+1]+=1\n",
    "                #print(\"有\",i,x,i-(x-1),i+1)\n",
    "            else:\n",
    "                dif[i+1]+=1\n",
    "                dif[n-(x-1-i)]-=1\n",
    "                #print(\"无\",i,x,i+1,n-(x-1-i))\n",
    "            #print(dif)\n",
    "        res=k=-1\n",
    "        #print(dif)\n",
    "        for i in range(n):\n",
    "            if i>0:\n",
    "                dif[i]+=dif[i-1]\n",
    "            if dif[i]>res:\n",
    "                res=dif[i]\n",
    "                k=i\n",
    "        #print(dif)\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        scores = [0] * n\n",
    "        for i in range(n):\n",
    "            l, r = nums[i], n - 1  # target range\n",
    "            if i >= l:  # l <= i <= r, potentially two ranges\n",
    "                # rotate nums[i] from i to l, range [0, i - l]\n",
    "                scores[0] += 1\n",
    "                if i - l + 1 < n:\n",
    "                    scores[i - l + 1] -= 1\n",
    "            # consider the right range\n",
    "            l = max(l, i + 1)\n",
    "            if l <= r:\n",
    "                scores[i + 1] += 1  # move nums[i] to position n - 1\n",
    "                if i + 1 + r - l + 1 < n:  # move nums[i] to position l\n",
    "                    scores[i + 1 + r - l + 1] -= 1\n",
    "        max_score, k = scores[0], 0\n",
    "        for i in range(1, n):\n",
    "            scores[i] += scores[i - 1]\n",
    "            if scores[i] > max_score:\n",
    "                max_score, k = scores[i], i\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        left = [0]*N \n",
    "        right = [0]*N \n",
    "\n",
    "        for i in range(N):\n",
    "            n = nums[i]\n",
    "            if i>=n:\n",
    "                left[0]+=1\n",
    "                right[i-n]+=1\n",
    "                if i+1<N:\n",
    "                    left[i+1]+=1\n",
    "                    right[N-1]+=1\n",
    "            else:\n",
    "                left[i+1]+=1\n",
    "                right[i+N-n]+=1\n",
    "        cnt = 0\n",
    "        score = 0\n",
    "        ret = 0\n",
    "        for i in range(N):\n",
    "            cnt+=left[i]\n",
    "            if cnt>score:\n",
    "                score = cnt \n",
    "                ret = i \n",
    "            cnt-=right[i]\n",
    "        return ret \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        # 大彻大悟了  但是偷偷把代码删了 写不出来了吧 大彻大悟？ 笑笑不说话.\n",
    "        # 待翌日 抛去题解 尝试之\n",
    "        # -2 -3 1 0 4  >=0 3\n",
    "        # 3 -3 1 0 4  >=1 3\n",
    "        # 3 2 1 0 4 >=2 3\n",
    "        # 3 2 6 0 4 >=3 3\n",
    "        # 3 2 6 5 4 >=4 3\n",
    "        # 3 2 6 5 9 >=5 3  等于没轮调 不计入\n",
    "\n",
    "        # 解法二: 差分数组 \n",
    "        # -2 -2 1 -1 4\n",
    "        n = len(nums)\n",
    "        res = [0] * (n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            a = (i+1)%n\n",
    "            b = (i-x+n)%n\n",
    "            if a <= b:\n",
    "                res[a] += 1\n",
    "                res[b+1] -= 1\n",
    "            else:\n",
    "                res[0] += 1; res[b+1] -= 1\n",
    "                res[a] += 1; res[n] += 1\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            res[i] += res[i-1]\n",
    "            if res[i] > res[ans]:\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        l, r = SortedList(), SortedList(i - x for i, x in enumerate(nums))  # 将 nums 分成左右两部分考虑，l 会移动到 r 右侧\n",
    "        n = len(nums)\n",
    "        mx = base = sum(x >= 0 for x in r)\n",
    "        ans = 0\n",
    "        for k in range(n):\n",
    "            # l 中的元素移动后，每项都会增加 n - k\n",
    "            # r 中的元素移动后，每项都会减少 k\n",
    "            pl1 = l.bisect_left(-(n - k))\n",
    "            pl2 = l.bisect_left(0)  # l[pl1: pl2] 中的元素都会增加1分\n",
    "            pr1 = r.bisect_left(0)\n",
    "            pr2 = r.bisect_left(k)  # l[pl1: pl2] 中的元素都会减少1分\n",
    "            if base + (pl2 - pl1) - (pr2 - pr1) > mx:\n",
    "                mx = base + (pl2 - pl1) - (pr2 - pr1)\n",
    "                ans = k\n",
    "            l.add(k - nums[k])\n",
    "            r.remove(k - nums[k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList()\n",
    "        for k,v in enumerate(nums):\n",
    "            sd1.add(k-v)\n",
    "        len1 = len(nums)\n",
    "        curmax = -math.inf\n",
    "        curidx = -1\n",
    "        for i in range(len(nums)):\n",
    "            val1 = len1 - sd1.bisect_left(i)\n",
    "            if val1 > curmax:\n",
    "                curmax = val1\n",
    "                curidx = i\n",
    "            sd1.remove(i - nums[i])\n",
    "            sd1.add(i - nums[i] + len1)\n",
    "        return curidx\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.bestRotation([2,3,1,4,0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1 = SortedList()\n",
    "        sd2 = SortedList()\n",
    "        for k,v in enumerate(nums):\n",
    "            sd1.add(k-v)\n",
    "        len1 = len(nums)\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            res.append(len1 - sd1.bisect_left(i))\n",
    "            sd1.remove(i - nums[i])\n",
    "            sd1.add(i - nums[i] + len1)\n",
    "        return res.index(max(res))\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.bestRotation([2,3,1,4,0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        sd=SortedList()\n",
    "        n=len(nums)\n",
    "        nums=nums+nums[:-1]\n",
    "        # print(nums)\n",
    "        t=0\n",
    "        cnt=0\n",
    "        res=0\n",
    "        mx=0\n",
    "        for i in range(n*2-1):\n",
    "            sd.add((i-nums[i],nums[i],i))\n",
    "            if i>=n-1:\n",
    "                # print(sd)\n",
    "                idx=sd.bisect_left((cnt,))\n",
    "                if n-idx>mx:\n",
    "                    mx=n-idx\n",
    "                    res=i-n+1\n",
    "                sd.remove((i-n+1-nums[i-n+1],nums[i-n+1],i-n+1))\n",
    "                cnt+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestRotation(self, nums: List[int]) -> int:\n",
    "\n",
    "        d = Counter()\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num <= i:\n",
    "                cnt += 1\n",
    "            d[i - num] += 1\n",
    "        mx = cnt\n",
    "        ans = 0\n",
    "        cur = cnt\n",
    "        for i in range(1, n):\n",
    "            cur -= d[i - 1]\n",
    "            cur += int(nums[i - 1] <= n - 1)\n",
    "            if cur > mx:\n",
    "                mx = cur\n",
    "                ans = i\n",
    "            d[n - 1 - nums[i - 1] + i] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
